/***************************************************************************
 * 
 * Copyright (c) 2012 Baidu.com, Inc. All Rights Reserved
 * common.h,v 1.0 2012-09-01 15:58 yelu01
 * 
 **************************************************************************/
 
 
 
/**
 * @file mem_matrix.cpp
 * @author yelu01(yelu01@baidu.com)
 * @date 2012-09-01 15:58
 * @version 1.0 
 * @brief matrix operation in memory using skiplit.
 *  
 **/

#include "mem_matrix.h"

node_t::node_t()
{
	item.reset();
	nexts = NULL;
}

mem_matrix_t::mem_matrix_t(comparator row_cmp, comparator col_cmp)
{
	this->_row_cmp = row_cmp;
	this->_col_cmp = col_cmp;
	_head = NULL;
	_height = 1;
	_size = 0;
}

mem_matrix_t::~mem_matrix_t()
{
	pnode p = _head;
	while(p)
	{
		pnode next = (p->nexts)[0];
		delete p->nexts;
		delete p;
		p = next;
	}
}

int mem_matrix_t::create()
{
	auto_mutex_t auto_mutex(_mutex);
	_height = 1;
	_head = new(std::nothrow) node_t;
	CHECK_NOT_NULL(_head, return -1, "failed to new node_t");
	// create an array of node_t* for head.next.
	_head->nexts = new(std::nothrow) pnode[_max_level_cnt];
	CHECK_NOT_NULL(_head->nexts, return -1, "failed to resize head nexts");
	for(uint32_t i = 0; i < _max_level_cnt; i++)
	{
		((_head->nexts)[i]) = NULL;
	}
	return 0;
}

int mem_matrix_t::insert(const pitem& item)
{
	auto_mutex_t auto_mutex(_mutex);
	CHECK_TRUE(item, return -1, "item is null ptr.");
	// Do remember to change time stamp here, otherwise, wrong location will be
	// found when searching for place to insert since default time stamp is 0
	// which will be "bigger"(in context of item compare function) than any
	// other time stamp.
	item->timestamp = get_curr_time_us();
	long long int k = _height;
	pnode update[_max_level_cnt] = {NULL};
	pnode p = _head, q = NULL;

	// searching for the position to insert by looping bypass every layer.
	item_less_cmp less_cmp(_row_cmp, _col_cmp);
	while(--k >= 0)
	{
		while(p && ((p == _head) || less_cmp(p->item, item)))
		{
			q = p; p = p->nexts[k];
		}
		// we have finished searching the k-th layer, remember the pointer.
		update[k] = q;
		p = q;
	}

	// Here, we have found the position to insert. Check if equality.
	//if(q && q != _head && !less_cmp(q->item, item) && !less_cmp(item, q->item))
	//{
	//	LOG(WARNING, "failed to insert, duplicate items found.");
	//	return -1;
	//};

	// Gen a random level, if it is greater than current level, change current
	// level.
	uint32_t new_k = _gen_random_height();
	for(uint32_t i = _height; i < new_k; i++)
	{
		update[i] = _head;
	}
	// Node need to lock _level. Under concurrent writing and reading circumstance,
	// the reader will either read the old level or the new level. Both of them
	// will not cause a crash. In addition, this is an atomic assignment.
	if(new_k > _height)
	{
		LOG(DEBUG, "new height.[old:%u][new:%u]", _height, new_k);
		_height = new_k;
	}

	// Now insert the new item.
	// Note: in order to guarantee concurrent write and read safety, the safest
	// way is to modify item.next to the right node_t, then modify the pointer
	// pointing to newly inserted item.
	pnode new_node = new(std::nothrow) node_t;
	CHECK_NOT_NULL(new_node, return -1, "failed to new node_t");
	new_node->nexts = new(std::nothrow) pnode[new_k];
	CHECK_NOT_NULL(new_node->nexts, return -1, "failed to new new_node->nexts");
	new_node->item = item;
	for(uint32_t i = 0; i < new_k; i++)
	{
		// this is an atomic assignment.
		new_node->nexts[i] = update[i]->nexts[i];
	}
	for(uint32_t i = 0; i < new_k; i++)
	{
		update[i]->nexts[i] = new_node;
	}
	_size++;
	return 0;
}

int mem_matrix_t::find(const bytes_t& row, std::vector<pitem>& res)
{
	// If list is empty. Return immediately.
	if(_head->nexts[0] == NULL)
	{
		return -1;
	}
	long long int k = _height;
	pnode update[_max_level_cnt] = {NULL};
	pnode p = _head, q = NULL;

	// searching for the first row which is greater or eq to row.
	while(--k >= 0)
	{
		while(p && ((p == _head) || _row_cmp(p->item->row, row)))
		{
			q = p; p = p->nexts[k];
		}
		// we have finished searching the k-th layer, remember the pointer.
		update[k] = q;
		p = q;
	}

	// check if p->nexts[0]->item->row is eq to row. if not, not found.
	p = p->nexts[0];
	row_ne_cmp row_ne(_row_cmp);
	if(!p || !(p->item) || row_ne(p->item->row, row)){ return -1; }

	// Item found. Now, p && p->item && p->item->row == row.
	row_eq_cmp row_eq(_row_cmp);
	item_eq_cmp item_eq(_row_cmp, _col_cmp);
	while(p && row_eq(p->item->row, row))
	{
		pitem first_item = p->item;
		while(p && item_eq(p->item, first_item))
		{
			p = p->nexts[0];
		}
		if(first_item)
		{
			res.push_back(first_item);
		}
	}
	return 0;
}

uint32_t mem_matrix_t::_gen_random_height()
{
	// Refer to leveldb. Increase height with probability 1 in kBranching
	static const uint32_t kBranching = 4;
	uint32_t height = 1;
	while(height < _max_level_cnt && ((std::rand() % kBranching) == 0))
	{
		height++;
	}
	assert(height > 0);
	assert(height <= _max_level_cnt);
	return height;
}

uint64_t mem_matrix_t::get_curr_time_us()
{
	struct timeval t;
	gettimeofday (&t, NULL);
	long long time_us = (long long)t.tv_sec * 1000000;
	time_us +=(long long) t.tv_usec;
	return (uint64_t)time_us;
}

mem_matrix_iterator_t::mem_matrix_iterator_t(mem_matrix_t& mem_matrix):
		_mem_matrix(mem_matrix)
{
	_curr_node = NULL;
	this->_row_cmp = _mem_matrix._row_cmp;
	this->_col_cmp = _mem_matrix._col_cmp;
	_is_reset = false;
}

int mem_matrix_iterator_t::reset()
{
	_is_reset = true;
	_curr_node = _mem_matrix._head->nexts[0];
	return 0;
}

int mem_matrix_iterator_t::get_next(pitem& item)
{
	// Sepcial operation for the first item.
	if(_is_reset)
	{
		if(NULL == _curr_node) { _is_reset = false; return -1; }
		item = _curr_node->item;
		_is_reset = false;
		return 0;
	}

	item_eq_cmp item_eq(_row_cmp, _col_cmp);
	pnode p = _curr_node;
	_curr_node = _curr_node->nexts[0];
	while(_curr_node && item_eq(_curr_node->item, p->item))
	{
		_curr_node = _curr_node->nexts[0];
	}
	if(NULL != _curr_node)
	{
		item = _curr_node->item;
		return 0;
	}

	// The end
	return -1;
}

uint64_t mem_matrix_iterator_t::size()
{
	// Remember to lock mem_matrix_t::_mu to avoid concurrent read and write.
	auto_mutex_t auto_mutex(_mem_matrix._mutex);
	uint64_t size = _mem_matrix._size;
	return size;
}
